package leetcode.list_problem;

/**
 * 234. 回文链表
 * https://leetcode-cn.com/problems/palindrome-linked-list/
 */
public class IsPalindrome {//中间节点和逆序的结合
    public boolean isPalindrome(ListNode head) {
        ListNode middle = middleNode(head);
        ListNode rexerseListNode = reverseList(middle);
        while ( head != null){
            if (rexerseListNode.val != head.val)
                return false;
            rexerseListNode = rexerseListNode.next;
            head = head.next;
        }
        return true;
    }
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null){//退出条件
            return head;
        }
        ListNode next = head.next;
        ListNode node = reverseList(head.next);//这个递归及其巧妙多看看他的head不是node
        next.next = head;//这里的head指向哪里一定要注意，画图理解一下
        head.next = null;
        return node;
    }
    public ListNode middleNode(ListNode head) {
        ListNode fast = head;
        ListNode low = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            low = low.next;
        }
        return low;
    }
}
